package pro.softzhang.algo.lc100;

import pro.softzhang.algo.flag.knowledge.KBackTracking;
import pro.softzhang.algo.flag.theme.TPalindrome;

import java.util.*;

/**
 *
 */
@KBackTracking
@TPalindrome
public class LC131_PalindromePartitioning {
    public static void main(String[] args) {

    }

    /**
     *
     */
    static
    class Solution {
        public String[][] partition(String s) {
            List<List<String>> r = new LinkedList<>();

            doPartition(s, 0, new LinkedList<>(), r);

            String[][] resArr = new String[r.size()][];
            for(int i = 0; i < r.size(); i++){
                List<String> list = r.get(i);
                resArr[i] = list.toArray(new String[list.size()]);
            }
            return resArr;

        }

        private void doPartition(String str, int start, LinkedList<String> subStrs, List<List<String>> r) {
            if(start == str.length()) {
                r.add(new LinkedList<>(subStrs));
                return;
            }

            for (int i = start; i < str.length(); i++) {
                if(isPalindrome(str, start, i)) {
                    subStrs.add(str.substring(start, i + 1));
                    doPartition(str, i + 1, subStrs, r);
                    subStrs.removeLast();
                }
            }
        }

        private boolean isPalindrome(String str, int start, int end) {
            while (start < end) {
                if(str.charAt(start++) != str.charAt(end--)) {
                    return false;
                }
            }
            return true;
        }
    }

    /**
     *
     */
    static
    class Solution1 {
        public List<List<String>> partition(String s) {
            List<List<String>> answer = new ArrayList<>();
            dfs(0, s, new LinkedList<>(), answer);
            return answer;
        }

        private void dfs(int i, String s, LinkedList<String> path, List<List<String>> answer) {
            if(i == s.length()) {
                answer.add(new ArrayList<>(path));
                return;
            }

            for(int j = i; j < s.length(); j++) {
                String t = s.substring(i, j + 1);
                if (isPalindrome(t)){
                    path.add(t);
                    dfs(j + 1, s, path, answer);
                    path.removeLast();
                }
            }
        }

        private boolean isPalindrome(String str) {
            int start = 0, end = str.length() - 1;
            while (start < end) {
                if(str.charAt(start++) != str.charAt(end--)) {
                    return false;
                }
            }
            return true;
        }
    }
}
